public class MinimumPathSum {

    /**
     * 给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
     * 说明：每次只能向下或者向右移动一步。
     * @param grid
     * @return
     */
    public int minPathSum(int[][] grid) {
        if (grid==null||grid.length==0||grid[0].length==0){
            return 0;
        }
        int[][] pathSum = new int[grid.length][grid[0].length];
        pathSum[0][0] = grid[0][0];
        for (int i=1;i<grid.length;i++){
            pathSum[i][0] = grid[i][0]+pathSum[i-1][0];
        }
        for (int j =1;j<grid[0].length;j++){
            pathSum[0][j] = grid[0][j]+pathSum[0][j-1];
        }
        for (int i=1;i<grid.length;i++){
            for (int j=1;j<grid[0].length;j++){
                pathSum[i][j] = Math.min(pathSum[i-1][j],pathSum[i][j-1])+ grid[i][j];
            }
        }


        return pathSum[grid.length-1][grid[0].length-1];

    }
}
